The smallest grammar problem is the problem of finding the smallest formal grammar which encodes for a unique string of characters. The size of a grammar is defined by the number of symbols on the right side of the production rules.